Problem statement: zenit17skh

Hrať sa je nuda

Počet bodov: 40, časový limit: 2000ms

Hry sú mrhanie časom – hra je prakticky opakom produktívnej činnosti. Mário sa nerád hrá – radšej bude pilne študovať, pracovať, športovať, a ak mu vyjde čas nazvyš, radšej pôjde spať – veď potom toho zajtra zvládne spraviť viac.

Napriek tomu sa hrám úplne vyhnúť nedá. Jeho spolubývajúci má obľúbenú hru a každý deň dobiedza do Mária, aby si ju zahral. Napokon Máriovi sľúbil, že v každý deň, čo si ju s ním zahrá, bude riad umývať on. To sa niekedy aj oplatí – ale len vtedy, keď Mário dokáže dostatočne rýchlo vyhrať.

Hra sa hrá na hracej doske rozmerov \(20 \times 20\). Na začiatku si postupne obaja hráči umiestnia na dosku svojich \(n\) žetónikov. Následne sa hrá podľa komplikovaných pravidiel, ktoré vás však nemusia zaujímať – hneď, ako Mário a jeho spolubývajúci doukladajú svoje žetóniky, Mário si zvolí vyhrávajúcu stratégiu a zistí, na akej pozícií skončia jeho žetóniky, keď povyhadzuje všetky súperove.

Následne mu stačí vrátiť svoje žetóniky na pozície, s ktorými začínal. V jednom ťahu môže žetónik posunúť o jedno políčko v ľubovoľnom zo štyroch základných smerov (ak je prázdne a nie je mimo hracej dosky); ak však na tomto políčku leží ďalší z jeho žetónikov, môže ho preskočiť a tým svoj žetónik posunúť o dve políčka v tomto smere (opäť, toto políčko musí byť prázdne a nie mimo hracej dosky). Viac ako jeden žetónik však preskočiť nemôže.

Hraciu dosku na začiatku tejto druhej fázy si môžete pozrieť na obrázku.

Ukážka herného plánu. Na obrázku je zobrazený iba ľavý horný roh \(8 \times 8\). Šípkami sú znázornené možné pohyby jedného zo žetónikov.

Mário chce rýchlo vedieť, či dokáže druhú fázu vyhrať na najviac \(k\) ťahov. Kedže písať program zaoberajúci sa hrou je ešte neproduktívnejšie ako samotné jej hranie, túto úlohu zveril vám.

Vstup a výstup

V prvom riadku vstupu sú dve celé čísla \(n\) a \(k\). V druhom riadku vstupu je za sebou \(n\) rôznych dvojíc čísel \(1 \leq x,y \leq 20\): súradnice Máriových žetónikov na začiatku hry. V treťom riadku vstupu sú v rovnakom formáte súradnice Máriových žetónikov na začiatku druhej fázy hry. Žetóniky sú nerozlíšiteľné, teda jednotlivé žetóniky nemusia skončit na súradniciach, na ktorých začínali.

Ak dokáže Mário dostať žetóniky naspäť na začiatocné pozície na najviac \(k\) ťahov, vypíšte Mario hraj!. V opačnom prípade vypíšte Mario umyvaj riad!.

V prvej sade \(n = 1\) a \(1 \leq k \leq 12\). V druhej sade \(n = 2\) a \(1 \leq k \leq 5\) V tretej sade \(n = 4\) a \(1 \leq k \leq 8\). V štvrtej sade \(n = 4\) a \(1 \leq k \leq 10\). V piatej sade \(n = 4\) a \(1 \leq k \leq 12\).

 Príklady

Input:

1 4
1 1
3 2

Output:

Mario hraj!

Príklad vstupu z prvej sady

Input:

2 3
3 3 3 4
3 6 3 7

Output:

Mario hraj!

Input:

2 3
3 3 3 4
3 6 3 8

Output:

Mario umyvaj riad!

Input:

4 8
8 6 9 6 11 10 11 11
7 3 8 6 11 12 13 12

Output:

Mario hraj!

Input:

4 8
8 6 9 6 11 10 11 11
7 2 8 6 11 12 13 12

Output:

Mario umyvaj riad!